#include <stdio.h>
#include <stack>

using namespace std;
namespace JIANZHI_OFFER
{
	bool IsPopOrder(int* pPush, int * pPop, int length)
	{
		stack<int> stackData;
		int p1 = 0, p2 = 0;
		if (pPush == NULL || pPop == NULL || length <= 0)
			return false;
		while (p2 < length)
		{
			while (stackData.empty() || stackData.top() != pPop[p2])
			{
				if (p1 >= length)
					break;
				stackData.push(pPush[p1]);
				++p1;
			}
			if (stackData.top() == pPop[p2])
			{
				stackData.pop();
				++p2;
			}
			else
				return false;
		}
		if (stackData.empty() && p1 == length && p2 == length)
			return true;
		else
			return false;
	}

	void TestInOrderPop()
	{
		int push[5] = {1,2,3,4,5};
		int pop[5] = {1,2,3,4,6};

		if (IsPopOrder(push,pop,5))
			printf("is in order pop!\n");
		else
			printf("is not in order pop!\n");
	}
}
